/* 线段树 区间修改
区间修改需要懒标记
* 1.原理
    满二叉树，用一维数组存整棵树

    当前编号是x, 父节点 x >> 1
                左孩子 2x
                右孩子 2x+1

    除最后一层外我们有2n−1个节点
    最后一层最多有2n个节点
    总的节点数不会超过4n−1个节点

* 2.操作
    push_up：由子节点计算父节点
    build：将一段区间初始化成线段树
    modify：修改操作 —— 修改单点或修改区间
    query：查询操作，即查询某一段线段树的信息
    push_down（懒标记、延迟标记）：由父节点计算子节点

* 3.build 构造
    //u：当前节点编号
    //l：当前区间的左端点
    //r：当前区间的右端点
    void build(int u, int L, int R)
    {      
        tree[u].l = L, tree[u].r = R; //将左右端点存入
        if(c == k) return; //如果当前节点为叶子节点，退出
        int mid = L + R >> 1; //计算当前区间中点
        build(u<<1, L, mid);
        build(u<<1|1, mid + 1, R);   
        //push_up(u);//一般会在此时进行push_up操作
        
    }

* 4.递归范围
    查询范围[L, R]
    (1)当前节点[Tl, Tr]整体被包含[L, R] <-> [Tl,Tr]⊂[L,R] <-> L <Tl < Tr < R 
    直接返回当前节点权值

    (2)存在交集, 但不全包含, 则向下递归

    (3)不存在交集, 不存在这种情况

* 5.区间修改 push_down
    懒标记(add) 给以当前节点为根的子树中的每一个节点(不包含根节点), 加上懒标记
    以区间和为例
    void push_down(int u)
    {
        auto &U = tree[u], &L = tree[L(u)], &R = tree[R(u)];
        L.laz += U.laz;
        L.sum += (L.r-L.l + 1) * U.laz;
        R.laz += U.laz;
        R.sum += (R.r-R.l + 1) * U.laz;
    }
    线段树永远只向下看

* 本题: 
    sum:如果考虑当前节点及子节点上的所有标记,当前区间和是多少
    懒标记mul, add: sum = sum*mul + add 先乘再加
        mul = mul * mul'; add = add * mul';
        add = add + add';
    
    优化 a = cx+b
    op1 *c: b=0 x*c+b->x*c
    op2 +b: c=1 x*1+b->x+b
    (x*a+b)*c+d -> x*ac + bc+d
    L.mul *= U.mul; L.add = L.add*U.mul+U.add;
    R.mul *= U.mul; R.add = R.add*U.mul+U.add;
*/

// #define ONLINE_DUDGE
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define int long long
const int N = 1e5+10;
#define L(u) (u << 1) // 左孩子
#define R(u) (u << 1 | 1) // 右孩子
struct Node
{
    int l, r;
    int sum, add, mul; // 区间和 懒标记
}tree[N << 2];

int n, MOD, m, A[N];

inline void push_up(Node &U,Node &L, Node &R) // 函数重载
{
    U.sum = (L.sum + R.sum) % MOD;
}

inline void push_up(int u) // u的孩子节点更新u的权值
{
    push_up(tree[u], tree[L(u)], tree[R(u)]);
    
}

void update(Node &U, int add, int mul) {
    // 更新当前节点信息，及其对应的懒标记
    U.sum = (U.sum * mul + (U.r - U.l + 1) * add) % MOD;
    U.add = (U.add * mul + add) % MOD; // 见上述公式
    U.mul = (U.mul * mul) % MOD;
}

inline void push_down(int u)
{
    auto &U = tree[u], &L = tree[L(u)], &R = tree[R(u)];
    update(L, U.add, U.mul);
    update(R, U.add, U.mul);
    U.add = 0, U.mul = 1;
}

inline void build(int u, int l, int r)
{      
    
    if(l == r) {tree[u] = {l, r, A[l], 0, 1}; return;}//如果当前节点为叶子节点，退出
    
    tree[u] = {l, r, 0, 0, 1}; //将左右端点存入
    int mid = tree[u].l + tree[u].r >> 1; //计算当前区间中点
    build(L(u), l, mid);
    build(R(u), mid + 1, r);   
    push_up(u);//一般会在此时进行push_up操作
}

inline int query(int u, int l, int r) 
{
    auto &U = tree[u], &L = tree[L(u)], &R = tree[R(u)];
    if(l <= U.l && U.r <= r) return U.sum; // 被完全包含

    push_down(u); // 向下传递懒标记
    int mid = (U.l + U.r) >> 1;
    int sum = 0;
    if(l <= mid) sum = query(L(u), l, r); // 与左区间有交集
    if(r > mid) sum = (sum + query(R(u), l, r)) % MOD; // 与右区间有交集
    return sum;
}

inline void modify(int u, int l, int r, int add, int mul) // 当前节点 修改区间左右端点 修改目标值
{
    auto &U = tree[u], &L = tree[L(u)], &R = tree[R(u)];
    if(l <= U.l && U.r <= r) {update(U, add, mul); return;}// 当前节点的区间被完全包含
    
    push_down(u); // 向下传递懒标记
    int mid = U.l + U.r >> 1;
    if(l <= mid) modify(L(u), l, r, add, mul);
    if(r > mid) modify(R(u), l, r, add, mul);
    push_up(u);
}

signed main()
{

    #ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);   
	cin.tie(0);
    #else
    freopen("./in.txt","r",stdin);
    #endif

    cin >> n >> MOD;
    for(int i = 1; i <= n; i++) cin >> A[i];
    cin >> m;

    build(1, 1, n);
    while(m--){
        int op, l, r; cin >> op >> l >> r;
        if(op == 1){ // *
            int d; cin >> d;
            modify(1, l, r, 0, d);
        }
        else if(op == 2){ // +
            int d; cin >> d;
            modify(1, l, r, d, 1);
        }
        else if(op == 3){
            cout << query(1, l, r) << endl;
        }
    }
    return 0;
}
